% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//4, height
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//4, height
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//4, height//4
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

%matplotlib notebook 

def calcGradient( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad

%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

%matplotlib notebook 

def calcGradient( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad

%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

xs = np.arange(height)
ys = np.array( [ 3 ** x for x in xs ] )

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.title("Computational Complexity")

xs = np.arange(height)
ys = np.array( [ 3 ** x for x in xs ] )

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
ys = np.array( [ 3 ** x for x in xs ] )

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
print(ys)

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
#print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
#print(ys)

ax.plot(xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
#print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
#print(ys)

ax.plot( ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(20)
#print(xs)
ys = np.array( [ 3 ** x for x in xs ] )
#print(ys)

ax.plot( xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(height)
#print(xs)
ys = [ 3 ** x for x in xs ]
#print(ys)

ax.plot( xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

fig = plt.figure()
ax = fig.add_subplot(1,1,1)
ax.set_title("Computational Complexity")

xs = np.arange(20)
#print(xs)
ys = [ 3 ** x for x in xs ]
#print(ys)

ax.plot( xs, ys, 'b-', linewidth=3 )

c1 = addJBFigure("c1", 0, 0, fig )
plt.close()

timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

display(HTML(t1imgT))

timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

display(HTML(f"""
<div style="background:grey">
{t1imgT}
</div>
""""))

timg = np.random.randint(0,99,(5,10))

t1imgT = createTable( timg )

display(HTML(f'<div style="background:grey">{t1imgT}</div>'))

%matplotlib notebook 

def findMinEnergySeam( grad ):
  height, width = grad.shape
  #print(grad.shape)
  carve = np.zeros((height, width))

  max = None
  carve[0,:] = grad[0,:]
  for y in range(1,height):
    for x in range(width):
      emin = None
      for tx, ty in [ [x-1, y-1], [x, y-1], [x+1, y-1] ]:
        if (tx >= 0) and ( tx < width ) and (ty >= 0 ) and (ty < height ):
          #print('tx',tx,'ty', ty, 'emin', emin, 'g[y,x]', grad[y,x], 'g[ty,tx]', grad[ty,tx] )
          if ( emin is None ) or ( grad[y,x] + grad[ty, tx] < emin ):
            emin = grad[y,x] + grad[ty, tx]
            #print('Setting emin', emin)
      carve[y,x] = emin
      if max is None or emin > max:
        max = emin
  return carve

carve = findMinEnergySeam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( carve, cmap = 'gray' )
sol1 = addJBFigure("sol1", 0, 0, fig )

%matplotlib notebook 

def findMinEnergySeam( grad ):
  height, width = grad.shape
  #print(grad.shape)
  carve = np.zeros((height, width))

  max = None
  carve[0,:] = grad[0,:]
  for y in range(1,height):
    for x in range(width):
      emin = None
      for tx, ty in [ [x-1, y-1], [x, y-1], [x+1, y-1] ]:
        if (tx >= 0) and ( tx < width ) and (ty >= 0 ) and (ty < height ):
          #print('tx',tx,'ty', ty, 'emin', emin, 'g[y,x]', grad[y,x], 'g[ty,tx]', grad[ty,tx] )
          if ( emin is None ) or ( grad[y,x] + grad[ty, tx] < emin ):
            emin = grad[y,x] + grad[ty, tx]
            #print('Setting emin', emin)
      carve[y,x] = emin
      if max is None or emin > max:
        max = emin
  return carve

carve = findMinEnergySeam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( carve, cmap = 'gray' )
sol1 = addJBFigure("sol1", 0, 0, fig )

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )         
sol2 = addJBFigure( "sol2", 0, 0, fig )       

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  c = min_index
  path = [c]
  print( f'Found minimum start', min_index, min)

p = greedy_seam(t1img)

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  c = min_index
  path = [c]
  print( f'Found minimum start', min_index, min)

p = greedy_seam(timg)

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None

    for dx in [-1, 0, 1]:
      xd = x +dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
      path.append(xd)
  return path
  
p = greedy_seam(timg)

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None

    for dx in [-1, 0, 1]:
      xd = x +dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
      path.append(xd)
  return path

p = greedy_seam(timg)
print('path', p)

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg)
print('path', p)

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg[:,1:10])
print('path', p)

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10]))

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append(x)
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10], p))

p = findMinEnergySeam( timg[:,1:10] )
print(p)

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(createTable(carve) ) )

p = findPath( carve )

print(p)

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print(p)

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print('Path', p, 'Energy', calc_energy(p) )

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print('Path', p, 'Energy', calc_energy(timg[:,1:10], p) )

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in p.reverse() ]
print(p2)
print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in reverse(p) ]
print(p2)
print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in reversed(p) ]
print(p2)
print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

p2 = [ p2 for p1,p2 in reversed(p) ]

print('Path', p, 'Energy', calc_energy(timg[:,1:10], p2 ) )

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [x]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append((y,x))
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10], p))

def greedy_seam( img ):
  height, width = len(img), len(img[0])
  min = None
  min_index = None
  for x in range(width):
    if min is None or img[0][x] < min:
      min_index = x
      min = img[0][x]
  
  x = min_index
  path = [(0,x)]
  for y in range(1,height):
    min = None
    min_index = None
    x2 = None
    for dx in [-1, 0, 1]:
      xd = x + dx
      if ( xd >= 0 ) and ( xd < width):
        if min is None or img[y][xd] < min:
          min = img[y][xd]
          x2 = xd
    x = x2
    path.append((y,x))
  return path

p = greedy_seam(timg[:,1:10])
print('path', p, 'energy', calc_energy(timg[:,1:10], p))

%matplotlib notebook 

def findMinEnergySeam( grad ):
  height, width = grad.shape
  #print(grad.shape)
  carve = np.zeros((height, width))

  max = None
  carve[0,:] = grad[0,:]
  for y in range(1,height):
    for x in range(width):
      emin = None
      for tx, ty in [ [x-1, y-1], [x, y-1], [x+1, y-1] ]:
        if (tx >= 0) and ( tx < width ) and (ty >= 0 ) and (ty < height ):
          #print('tx',tx,'ty', ty, 'emin', emin, 'g[y,x]', grad[y,x], 'g[ty,tx]', grad[ty,tx] )
          if ( emin is None ) or ( grad[y,x] + grad[ty, tx] < emin ):
            emin = grad[y,x] + grad[ty, tx]
            #print('Setting emin', emin)
      carve[y,x] = emin
      if max is None or emin > max:
        max = emin
  return carve

carve = findMinEnergySeam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( carve, cmap = 'gray' )
sol1 = addJBFigure("sol1", 0, 0, fig )

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = greedy_seam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )         
sol2 = addJBFigure( "sol2", 0, 0, fig )       

carve = findMinEnergySeam( timg[:,1:10] )

display( HTML(f'<div style="background:grey">{createTable(carve)}</div>' ) )

p = findPath( carve )

print('Path', p, 'Energy', calc_energy(timg[:,1:10], p ) )

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = greedy_seam( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = np.array( greedy_seam( grad ) )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=3 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = np.array( greedy_seam( grad ) )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=7 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

% matplotlib notebook 
def findPath( carve ):
  height, width = carve.shape
  minIndex = None
  min = None
  for x in range(width):
    if min is None or carve[height-1, x] < min:
      minIndex = x
      min = carve[height-1, x]
  
  cx = minIndex
  path = [ [ height-1, cx]]
  
  for y in range( height-2, -1, -1 ):
    min = None
    minX = None
    for dx in [ cx-1, cx, cx+1 ]:
      if ( dx >= 0 ) and ( dx < width ):
        if min is None or carve[y,dx] < min:
          min = carve[y,dx]
          minX = dx
    cx = minX
    path.append([ y, cx ] )
  return path

carve = findMinEnergySeam( grad )
minPath = np.array( findPath(carve) )
#print(minPath )

greedyPath = np.array( greedy_seam( grad ) )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg )
ax.plot( minPath[:,1], minPath[:,0], 'b-', linewidth=7 )
ax.plot( greedyPath[:,1], greedyPath[:,0], 'g-', linewidth=3 )

sol2 = addJBFigure( "sol2", 0, 0, fig )       

def removePath( img, path ):
  height, width, depth = img.shape
  new = np.zeros((height, width-1, depth))
  #print(img.shape, new.shape)

  for y,x in path:
    #r = img[y,:x+1] + img[y,x+1:]
    #print('x',x)
    new[y,0:x] = img[y,0:x]
    new[y,x:] = img[y,x+1:]
  return new

def carveSeam(origImg, NIter ):
  img = origImg.copy()
  for i in range(NIter):
    #print('Loop', i, 'Shape', img.shape)
    grad = calcGradient( img )
    carve = findMinEnergySeam( grad )
    minPath = np.array( findPath(carve) )
    #print('grad', grad.shape, 'carve', carve.shape, 'path', minPath[0:5] )
    img = removePath( img, minPath )

    # img = np.rot90( img )
    # grad = calcGradient( img )
    # carve = findMinEnergySeam( grad )
    # minPath = np.array( findPath(carve) )
    # #print('grad', grad.shape, 'carve', carve.shape, 'path', minPath[0:5] )
    # img = removePath( img, minPath )
    # img = np.rot90( img, 3 )
    
  return img.astype(np.uint8)

height, width, depth = oimg.shape
NIter = 100
simg = carveSeam( oimg, NIter )
print('simg', simg.shape)

fig = plt.figure( figsize=(12,10))
ax1 = fig.add_subplot(1,3,1)

ax1.imshow( oimg )

ax2 = fig.add_subplot(1,3,2)

ax2.imshow( simg )

ax3 = fig.add_subplot(1,3,3)
ax3.imshow( origImage.resize((width - NIter, height - NIter)))

sol10 = addJBFigure( "sol10", 0, 0, fig )

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

%matplotlib notebook 

def calcGradientSlow( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad

% matplotlib notebook 

import matplotlib.pyplot as plt
from PIL import Image
import numpy as np
import math
import random

origImage = Image.open( img1.getLocalName() )
width, height = origImage.size

nw, nh = width//2, height//2
origImage = origImage.resize((nw,nh))
oimg = np.array( origImage )
#oimg = oimg[200:300,430:530]

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( oimg, cmap='gray')

balir=addJBFigure("balir", 0, 0, fig )

%matplotlib notebook 

def calcGradientSlow( img ):
  height, width, depth = img.shape
  grad = np.zeros( ( height, width )  )
  #print(height, width, depth )
  for y in range( height ):
    for x in range( width ):
      gx, cnt = 0.0, 0
      for dx, dy in [ [-1,-1], [0,-1], [1,-1], [-1,0], [1,0], [1,-1], [1,0], [1,1] ]:
        x1 = x + dx
        y1 = y + dy
        if ( x1 >= 0 ) and ( x1 < width ) and ( y1 >= 0 ) and ( y1 < height ):
          d = np.sum( np.abs( img[y,x] - img[y1,x1] ) )
          
          gx = gx + d
          cnt = cnt + 1
      grad[y,x] = gx/cnt
  return grad

%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )

%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )

%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )

%matplotlib notebook 

def normalizeImage( img ):
  return ( grad - np.min(grad) ) * 255.0 / np.max(grad)

#img = np.random.random( (10,10,3) ) *255
#img[0:10,5:8,:] = 128

grad = calcGradient( oimg )
print('grad shape', grad.shape)
gradNorm = normalizeImage( grad )

fig = plt.figure()
ax = fig.add_subplot(1,1,1)

ax.imshow( gradNorm, cmap = 'gray' )

bali10 = addJBFigure( "bali10", 0, 0, fig )